package LiKouBrushQuestions;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author 23737
 * @version 1
 */
public class July_1 {
    public static void main(String[] args) {
        System.out.println("祝福祖国生日快乐！！！！中国最棒");
//        TreeNode treeNode = new Solution().creatTreeNode(1);
//        System.out.println(new Solution().isSymmetric(treeNode));
    }
}

/**
 * @author 23737
 * @create 2021.7.1 19.10
 * 剑指offer27 二叉树的镜像
 */
class TreeNodeMirrorTree {
    int val;
    TreeNodeMirrorTree left;
    TreeNodeMirrorTree right;

    TreeNodeMirrorTree(int x) {
        val = x;
    }
}
//class Solution {
//    //利用递归来写
//    public TreeNode mirrorTree(TreeNode root) {
//        if (root == null) {
//            return null;
//        }
//        TreeNode left = mirrorTree(root.left);
//        TreeNode right = mirrorTree(root.right);
//        root.left = right;
//        root.right = left;
//        return root;
//    }
//}


//第二种做法 用栈来写（我觉得更好理解一点）
class SolutionmirrorTree {
    //利用栈来写
    public TreeNodeMirrorTree mirrorTree(TreeNodeMirrorTree root) {
        if (root == null) {
            return null;
        }
        Stack<TreeNodeMirrorTree> stack = new Stack<TreeNodeMirrorTree>() {
            {
                add(root);
            }
        };
        while (!stack.isEmpty()) {
            TreeNodeMirrorTree pop = stack.pop();
            if (pop.left != null) {
                stack.add(pop.left);
            }
            if (pop.right != null) {
                stack.add(pop.right);
            }
            TreeNodeMirrorTree temp = pop.left;
            pop.left = pop.right;
            pop.right = temp;
        }
        return root;
    }
}



/**
 * @time 2021.7.2
 * 剑指offer 28  对称的二叉树
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
class SolutionOne {
    public TreeNode creatTreeNode(int i){
        TreeNode treeNode = null;
        if(i==1){
            treeNode = new TreeNode(1);
            TreeNode treeNode1 = new TreeNode(2);
            TreeNode treeNode2 = new TreeNode(2);
            TreeNode treeNode3 = new TreeNode(3);
            TreeNode treeNode4 = new TreeNode(4);
            TreeNode treeNode5 = new TreeNode(4);
            TreeNode treeNode6 = new TreeNode(3);
            treeNode.left = treeNode1;
            treeNode.right = treeNode2;
            treeNode1.left=treeNode3;
            treeNode1.right = treeNode4;
            treeNode2.left = treeNode5;
            treeNode2.right = treeNode6;
        }else if(i==2){
            treeNode = new TreeNode(1);
            TreeNode treeNode1 = new TreeNode(2);
            TreeNode treeNode2 = new TreeNode(2);
            TreeNode treeNode3 = new TreeNode(3);
            TreeNode treeNode4 = new TreeNode(3);
            treeNode1.right=treeNode3;
            treeNode2.right=treeNode4;
            treeNode.left=treeNode1;
            treeNode.right=treeNode2;
        }
        System.out.println(treeNode);
        return treeNode;
    }
    public boolean isSymmetric(TreeNode root) {
        TreeNode original = root;
        if (root == null) {
            return false;
        }
        Stack<TreeNode> stack = new Stack<>() {
            {
                add(root);
            }
        };
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.left != null) {
                stack.add(pop.left);
            }
            if (pop.right != null) {
                stack.add(pop.right);
            }
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
        if (root == original){
            return true;
        }
        return false;
    }
}
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}




